/*
* leetcode 3261. 统计满足 K 约束的子字符串数量 II
*
给你一个 二进制 字符串 s 和一个整数 k。
另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。
如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：
字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。
返回一个整数数组 answer ，其中 answer[i] 表示 s[li..ri] 中满足 k 约束 的
子字符串的数量。
/*
* */
import java.util.*;
class Solution {
    public long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
        char[] cs=s.toCharArray();
        int n=queries.length,len=s.length();
        long[] ret=new long[n],sum=new long[len+1];
        int[] ri=new int[len];
        Arrays.fill(ri,len);
        int zero=0,one=0;
        for(int l=0,r=0;r<len;++r){
            if(cs[r]=='0')zero++;
            else one++;
            while(zero>k&&one>k){
                if(cs[l]=='0')zero--;
                else one--;
                ri[l]=r;
                l++;
            }
            sum[r+1]=sum[r]+r-l+1;
        }
        for(int i=0;i<n;i++){
            int l=queries[i][0],r=queries[i][1];
            int m=Math.min(ri[l],r+1);
            long x=(long)(m-l+1)*(m-l)/2;
            long y=sum[r+1]-sum[m];
            ret[i]+=(y+x);
        }
        return ret;
    }
}